/**
 * 
 */
package array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;

/**
 * @author Michael
 * 3 sum
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:
Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
The solution set must not contain duplicate triplets.
    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)
 * 
 * @since 01/24/2013
 * @version 01/24/2013
 * 
 */
public class ThreeSumAddingToGivenTarget {

	public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
		assert (num != null && num.length >= 3);

		Arrays.sort(num);
		HashSet<ArrayList<Integer>> set = new HashSet<ArrayList<Integer>>();
		for (int i = 0; i < num.length - 2; i++) {
			int target = 0 - num[i];
			int left = i + 1;
			int right = num.length - 1;
			while (left < right) {
				int sum = num[left] + num[right];
				if (sum == target) {
					ArrayList<Integer> arr = new ArrayList<Integer>();
					arr.add(num[i]);
					arr.add(num[left++]);
					arr.add(num[right--]);
					set.add(arr);
				} else if (sum < target) {
					left++;
				} else {
					right--;
				}
			}
		}

		return new ArrayList<ArrayList<Integer>>(set);
	}

	// Time O(n^2), Space O(1)
	public static void findTuples(int[] arr, int target) {
		assert (arr != null);

		if (arr.length < 3) {
			return;
		}

		Arrays.sort(arr);
		for (int first = 0; first < arr.length - 2; ++first) {
			int second = first + 1;
			int third = arr.length - 1;
			int key = target - first;
			while (second < third) {
				int sum = arr[second] + arr[third];
				if (sum == key) {
					System.out.printf("(%d, %d, %d) = %d)\n", arr[first],
							arr[second], arr[third], target);
					second++;
					third--;
				} else if (sum < key) {
					++second;
				} else {
					--third;
				}
			}
		}
	}

	/**
	 * 
	 */
	public ThreeSumAddingToGivenTarget() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		ThreeSumAddingToGivenTarget tsatgt = new ThreeSumAddingToGivenTarget();
		int[] s = { -1, 0, 1, 2, -1, -4 };
		ArrayList<ArrayList<Integer>> result = tsatgt.threeSum(s);
		for (ArrayList<Integer> al : result) {
			for (int i : al) {
				System.out.printf("%d ", i);
			}
			System.out.println();
		}

		// int[] a = CreateUtils.randNonNegIntArray(10, 10);
		// int target = CreateUtils.randNonNegInt(20);
		// PrintUtils.printArray(a);
		// System.out.println(target);
		// findTuples(a, target);
	}

}

class Tuple {
	private int a, b, c;

	public Tuple(int x, int y, int z) {
		int[] arr = new int[3];
		arr[0] = x;
		arr[1] = y;
		arr[2] = z;
		Arrays.sort(arr);
		a = arr[0];
		b = arr[1];
		c = arr[2];
	}

	@Override
	public boolean equals(Object o) {
		if (this == o) {
			return true;
		}
		if (!(o instanceof Tuple)) {
			return false;
		}

		Tuple t = (Tuple) o;
		return (a == t.a && b == t.b && c == t.c);
	}

	@Override
	public int hashCode() {
		return ((a * 13) + b) * 13 + c;
	}

	public ArrayList<Integer> toList() {
		ArrayList<Integer> list = new ArrayList<Integer>(3);
		list.add(a);
		list.add(b);
		list.add(c);
		return list;
	}

	public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
		ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
		HashSet<Tuple> dedup = new HashSet<Tuple>();

		if (num.length < 3)
			return result;
		Arrays.sort(num);
		int len = num.length;
		for (int i = 0; i < len; i++) {
			if (i > 0 && num[i] == num[i - 1])
				continue;

			int target = -num[i];
			int left = 0, right = len - 1;
			while (left < right) {
				if (left == i) {
					left++;
					continue;
				}
				if (right == i) {
					right--;
					continue;
				}
				int sum = num[left] + num[right];
				if (sum == target) {
					Tuple newTuple = new Tuple(num[i], num[left], num[right]);
					if (!dedup.contains(newTuple)) {
						dedup.add(newTuple);
						result.add(newTuple.toList());
					}
					left++;
					right--;
				} else if (sum < target) {
					left++;
				} else {
					right--;
				}
			}
		}

		return result;
	}

}
